/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class ReplaceWords {

	class Node {
		Node[] next = new Node[26];
		boolean isEnd;

		public void add(String d) {
			Node cur = this;
			for (int i = 0; i < d.length(); i++) {
				char ch = d.charAt(i);
				if (cur.next[ch - 'a'] == null) {
					cur.next[ch - 'a'] = new Node();
				}
				cur = cur.next[ch - 'a'];
			}
			cur.isEnd = true;
		}

		public String search(String string) {
			Node cur = this;
			for (int i = 0; i < string.length(); i++) {
				char ch = string.charAt(i);
				if (cur.next[ch - 'a'] == null) {// 找不到匹配
					return string;
				} else {// 找到
					cur = cur.next[ch - 'a'];
					if (cur.isEnd) {
						return string.substring(0, i + 1);
					}
				}
			}
			return string;
		}
	}

	public String replaceWords(List<String> dict, String sentence) {
		Node root = new Node();
		for (String d : dict) {
			root.add(d);
		}
		String[] strings = sentence.split(" ");

		String reString = "";
		for (String string : strings) {
			String reString2 = root.search(string);
			reString += reString2 + " ";
		}
		return reString.substring(0, reString.length() - 1);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] strings = { "cat", "bat", "rat" };
		List<String> dict = new ArrayList<>();
		for (String string : strings) {
			dict.add(string);
		}
		String string = "the cattle was rattled by the battery";
		System.out.println(new ReplaceWords().replaceWords(dict, string));

	}

}
